#include <stdio.h>

int array[] = {5, 1, 8, 12, 32, 9,
			   7, 21, 16, 18, 14, 11,
			   9, 0, 2, 4, 22, 17};

#define ARRAY_LENGTH sizeof(array) / sizeof(int)


void print_array();

/**
 * 快速排序
 * @param left 开始索引
 * @param right 结束索引
 */
void quick_sort(int left, int right);

/**
 * 快速排序使用一种分治的方法来排序。它把一个列表分成两个部分（左边和右边），
 * 其中左部分只包含比某个值小的数，右部分只包含比某个值大的数。这个值被插在两部分的中
 * 间。当快速排序完成分割以后，那个值已经在一个正确的排序位置上（所以以后不需要处理
 * 它），同时也生成了两个列表，我们可以分别对它们进行排序而不用考虑另外的一个，这样
 * 就会形成一个排序的列表了。快速排序在两个分离的列表上工作，重复这个过程直到所有的
 * 值都在正确的位置上。
 */
int main() {
	// 打印原始数组
	print_array();
	// 快速排序
	quick_sort(0, ARRAY_LENGTH - 1);
	// 打印排序后的数组
	print_array();
}

void print_array() {
	printf("array: [");
	for (int i = 0; i < ARRAY_LENGTH; i++) {
		printf("%d, ", array[i]);
	}
	printf("\b\b]\n");
}

void quick_sort(int left, int right) {
	// 递归退出条件
	if (left < right) {
		// 基准值
		int pivot = array[right], i = left - 1, j = right;
		// 基于基准值，将数组分治排序
		while (1) {
			// 左侧大于等于基准值的索引
			while (array[++i] < pivot);
			// 右侧小于等于基准值的索引
			while (array[--j] > pivot);
			// 两侧索引位置没有相交，则交换
			if (i >= j) break;
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}

		// 将基准值放到正确的位置
		array[right] = array[i];
		array[i] = pivot;

		// 左侧递归
		quick_sort(left, i - 1);
		// 右侧递归
		quick_sort(i + 1, right);
	}
}